#include <vector>
#include "../common/DoublyListNode.h"

using namespace std;

/* 基于双向链表实现的双向队列 */
class LinkedListDeque {
private:
    DoublyListNode *front, *rear; // 头结点 front ，尾结点 rear
    int queSize = 0;              // 双向队列的长度

public:
    /* 构造方法 */
    LinkedListDeque() : front(nullptr), rear(nullptr) {}

    /* 析构方法 */
    ~LinkedListDeque() {
        freeMemoryLinkedList(front);
    }

    /* 获取双向队列的长度 */
    int size() {
        return queSize;
    }

    /* 判断双向队列是否为空 */
    bool isEmpty() {
        return size() == 0;
    }

    /* 入队操作 */
    void push(int num, bool isFront) {
        DoublyListNode *node = new DoublyListNode(num);
        if (isEmpty())
            front = rear = node;
        else if (isFront) {
            front->prev = node;
            node->next = front;
            front = node;
        } else {
            rear->next = node;
            node->prev = rear;
            rear = node;
        }
        queSize++;
    }

    /* 队首入队 */
    void pushFirst(int num) {
        push(num, true);
    }

    /* 队尾入队 */
    void pushLast(int num) {
        push(num, false);
    }

    /* 出队操作 */
    int pop(bool isFront) {
        if (isEmpty())
            return -1;
        int val;
        if (isFront) {
            val = front->val;
            DoublyListNode *fNext = front->next;
            if (fNext != nullptr) {
                fNext->prev = nullptr;
                front->next = nullptr;
                delete front;
            }
            front = fNext;
        } else {
            val = rear->val;
            DoublyListNode *rPrev = rear->prev;
            if (rPrev != nullptr) {
                rPrev->next = nullptr;
                rear->prev = nullptr;
                delete rear;
            }
            rear = rPrev;
        }
        queSize--;
        return val;
    }

    /* 队首出队 */
    int popFirst() {
        return pop(true);
    }

    /* 队尾出队 */
    int popLast() {
        return pop(false);
    }

    /* 访问队首元素 */
    int peekFirst() {
        return isEmpty() ? -1 : front->val;
    }

    /* 访问队尾元素 */
    int peekLast() {
        return isEmpty() ? -1 : rear->val;
    }

    /* 返回数组用于打印 */
    vector<int> toVector() {
        DoublyListNode *node = front;
        vector<int> res(size());
        for (int i = 0; i < res.size(); i++) {
            res[i] = node->val;
            node = node->next;
        }
        return res;
    }

    /* 遍历链表删除结点，释放内存 */
    void freeMemoryLinkedList(DoublyListNode* head)
    {
        DoublyListNode *pre, *cur = head;
        while (cur != nullptr) {
            pre = cur;
            cur = cur->next;
            delete pre;
        }
    }
};
